import java.util.Scanner;

public class LinearTimeSelection {
    /**
     * 线性时间选择方法，用于查找第k小的元素
     * 基于快速排序的思想，但是后面需要根据此主元的位置确定是查找左半部分、还是右半部分
     *
     */
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("输入排序数组的长度：");
        int n=in.nextInt();
        int[] arr=new int[n];
        System.out.print("依次输入数组元素： ");
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt();
        }
        System.out.println("输入需要查找位置：");
        int k=in.nextInt();

        int kthSmallest = linerSelect(arr, 0, arr.length - 1, k);

        System.out.println("第" + k + "小的元素是：" + kthSmallest);


    }

    public static int linerSelect(int []arr,int left,int right,int k){
        if(left==right){
            return arr[left];
        }
        int pivotIndex=partion(arr,left,right);

        int rank=pivotIndex-left+1;

        if(k==rank){
            return arr[pivotIndex];
        }else if(k<rank){
            return linerSelect(arr, left, pivotIndex-1, k);
        }else {
            return linerSelect(arr, pivotIndex+1, right, k-rank);
            //递归调用 linearSelect() 函数来在右半部分继续查找第k - rank小元素。
        }

        //第k大的元素
//        if (k == rank) {
//            return arr[pivotIndex];
//        } else if (k < rank) {
//            return linearSelect(arr, pivotIndex + 1, right, k); // 在右半部分继续查找第k大元素
//        } else {
//            return linearSelect(arr, left, pivotIndex - 1, k - rank); // 在左半部分继续查找第 k-rank 大元素
//        }
    }

    public static int partion(int []arr,int left,int right){
        int pivot=arr[right];
        int i=left-1;
        for(int j=left;j<right;j++){
            if(arr[j]<=pivot){
                // 找大的元素的话，将大于的数放在左边，符号改为>=

                i++;
                swap(arr,i,j);
            }
        }
        swap(arr,i+1,right);
        return i+1; //返回主元指定的位置
    }

    // 交换
    public static void swap(int []arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;

    }
}
